<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 数组二叉树（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>二叉树也可以用数组来存储&#xff0c;给定一个数组&#xff0c;树的根节点的值存储在下标1&#xff0c;对于存储在下标N的节点&#xff0c;它的左子节点和右子节点分别存储在下标2*N和2*N&#43;1&#xff0c;并且我们用值-1代表一个节点为空。</p> 
<p>给定一个数组存储的二叉树&#xff0c;试求<strong>从根节点到最小的叶子节点的路径</strong>&#xff0c;路径由节点的值组成。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入一行为数组的内容&#xff0c;数组的每个元素都是正整数&#xff0c;元素间用空格分隔。</p> 
<p>注意第一个元素即为根节点的值&#xff0c;即数组的第N个元素对应下标N&#xff0c;下标0在树的表示中没有使用&#xff0c;所以我们省略了。</p> 
<p>输入的树最多为7层。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出从根节点到最小叶子节点的路径上&#xff0c;各个节点的值&#xff0c;由空格分隔&#xff0c;用例保证最小叶子节点只有一个。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3 5 7 -1 -1 2 4</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3 7 2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">最小叶子节点的路径为3 7 2。</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">5 8 7 6</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">最小叶子节点的路径为5 8 7 6&#xff0c;注意数组仅存储至最后一个非空节点&#xff0c;故不包含节点“7”右子节点的-1。</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题有两种思路&#xff0c;一种是从树顶节点向下找&#xff0c;直到找到最小值节点。</p> 
<p>这种方式是典型的深度优先搜索。</p> 
<p><img alt="" height="442" src="https://img-blog.csdnimg.cn/44c155df2da9416394db3c3d03607f26.png" width="1200" /></p> 
<p></p> 
<p>还有一种思路是先找到最小值节点&#xff0c;然后从最小值节点向上找父节点&#xff0c;由于向上找只有一个父节点&#xff0c;因此只有一种路径。</p> 
<p>因此&#xff0c;我们应该选择这种方式。</p> 
<p><img alt="" height="442" src="https://img-blog.csdnimg.cn/352200e45d9d48e28ee01e9af8bfa341.png" width="1200" /></p> 
<p>采用这种方式&#xff0c;首先需要找到最小值节点在数组中的索引位置idx&#xff0c;然后根据题目定义的规则</p> 
<blockquote> 
 <p>对于存储在下标N的节点&#xff0c;它的左子节点和右子节点分别存储在下标2*N和2*N&#43;1</p> 
</blockquote> 
<p>当然上面这个规则是针对根节点索引从1开始的&#xff0c;如果根节点索引从0开始算法&#xff0c;则上面规则应变为</p> 
<blockquote> 
 <p>对于存储在下标N的节点&#xff0c;它的左子节点和右子节点分别存储在下标<span style="color:#fe2c24;">2*N&#43;1</span>和<span style="color:#fe2c24;">2*N&#43;2</span></p> 
</blockquote> 
<p>每找到一个父节点&#xff0c;就将其当成新的子节点&#xff0c;继续向上找父节点&#xff0c;直到子节点本身就是树顶节点为止。</p> 
<p></p> 
<p>另外&#xff0c;如何找到最小值叶子节点呢&#xff1f;</p> 
<p>我们可以反向遍历输入的节点数组&#xff0c;如果遍历的节点符合下面条件&#xff0c;那么他就是一个叶子节点&#xff1a;</p> 
<ul><li>自身节点值不为-1</li><li>自身没有子节点&#xff08;即既没有左子节点&#xff0c;也没有右子节点&#xff09;</li></ul> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  const arr &#61; line.split(&#34; &#34;).map(Number);
  let n &#61; arr.length - 1;
  // 最小叶子节点的值
  let min &#61; Infinity;
  // 最小节点在数组中的索引位置
  let minIdx &#61; -1;
  for (let i &#61; n; i &gt;&#61; 0; i--) {
    if (arr[i] !&#61; -1) {
      if (i * 2 &#43; 1 &lt;&#61; n &amp;&amp; arr[i * 2 &#43; 1] !&#61; -1) continue;
      if (i * 2 &#43; 2 &lt;&#61; n &amp;&amp; arr[i * 2 &#43; 2] !&#61; -1) continue;

      if (min &gt; arr[i]) {
        min &#61; arr[i];
        minIdx &#61; i;
      }
    }
  }

  // path用于缓存最小叶子节点到根的路径
  const path &#61; [];
  path.unshift(min);

  // 从最小值节点开始向上找父节点&#xff0c;直到树顶
  while (minIdx !&#61;&#61; 0) {
    let f &#61; Math.floor((minIdx - 1) / 2);
    path.unshift(arr[f]);
    minIdx &#61; f;
  }

  console.log(path.join(&#34; &#34;));
});
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    Integer[] arr &#61;
        Arrays.stream(sc.nextLine().split(&#34; &#34;)).map(Integer::parseInt).toArray(Integer[]::new);

    System.out.println(getResult(arr));
  }

  public static String getResult(Integer[] arr) {
    int n &#61; arr.length - 1;

    // 最小叶子节点的值
    int min &#61; Integer.MAX_VALUE;
    // 最小叶子节点的索引
    int minIdx &#61; -1;

    // 求解最小叶子节点的值和索引
    for (int i &#61; n; i &gt;&#61; 1; i--) {
      if (arr[i] !&#61; -1) {
        if (i * 2 &#43; 1 &lt;&#61; n &amp;&amp; arr[i * 2 &#43; 1] !&#61; -1) continue;
        if (i * 2 &#43; 2 &lt;&#61; n &amp;&amp; arr[i * 2 &#43; 2] !&#61; -1) continue;
        if (min &gt; arr[i]) {
          min &#61; arr[i];
          minIdx &#61; i;
        }
      }
    }

    // path用于缓存最小叶子节点到根的路径
    LinkedList&lt;Integer&gt; path &#61; new LinkedList&lt;&gt;();
    path.addFirst(min);

    // 从最小叶子节点开始向上找父节点&#xff0c;直到树顶
    while (minIdx !&#61; 0) {
      int f &#61; (minIdx - 1) / 2;
      path.addFirst(arr[f]);
      minIdx &#61; f;
    }

    StringJoiner sj &#61; new StringJoiner(&#34; &#34;);
    for (Integer val : path) sj.add(val &#43; &#34;&#34;);

    return sj.toString();
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import sys

# 输入获取
arr &#61; list(map(int, input().split()))


# 算法入口
def getResult(arr):
    # 最小叶子节点的值
    minV &#61; sys.maxsize
    # 最小节点在数组中的索引位置
    minIdx &#61; -1
    n &#61; len(arr) - 1

    for i in range(n, 0, -1):
        if arr[i] !&#61; -1:
            if i * 2 &#43; 1 &lt;&#61; n and arr[i * 2 &#43; 1] !&#61; -1:
                continue
            if i * 2 &#43; 2 &lt;&#61; n and arr[i * 2 &#43; 2] !&#61; -1:
                continue

            if minV &gt; arr[i]:
                minV &#61; arr[i]
                minIdx &#61; i

    # path用于缓存最小叶子节点到根的路径
    path &#61; []
    path.insert(0, str(minV))

    # 从最小值节点开始向上找父节点&#xff0c;直到树顶
    while minIdx !&#61; 0:
        f &#61; (minIdx - 1) // 2
        path.insert(0, str(arr[f]))
        minIdx &#61; f

    return &#34; &#34;.join(path)


# 算法调用
print(getResult(arr))
</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>